package dp;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N除数博弈1025.java
 * @Description https://leetcode-cn.com/problems/divisor-game/
 * @createTime 2021年12月02日 20:52:00
 *
 * 爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。
 *
 * 最初，黑板上有一个数字 n 。在每个玩家的回合，玩家需要执行以下操作：
 *
 * 选出任一 x，满足 0 < x < n 且 n % x == 0 。
 * 用 n - x 替换黑板上的数字 n 。
 * 如果玩家无法执行这些操作，就会输掉游戏。
 *
 * 只有在爱丽丝在游戏中取得胜利时才返回 true 。假设两个玩家都以最佳状态参与游戏
 *
 */
public class N除数博弈1025 {

	public boolean divisorGame(int N) {
		if (N == 1) {
			return false;
		}

		// 为了不处理下标偏移，多设置 1 格
		// dp[i]：黑板上的数字为 i 时，当前做出选择的人是否会赢
		boolean[] dp = new boolean[N + 1];
		// 最基本情况
		dp[1] = false;
		dp[2] = true;

		/**
		 *
		 */
		// 以线性的方式逐步递推得到结果
		for (int i = 3; i <= N; i++) {
			//步数
			for (int j = 1; j <= i / 2; j++) {
				// 只要做出的选择的其中之一，能让对方输，在当前这一步我们就可以赢
				if ((i % j == 0) && !dp[i - j]) {
					dp[i] = true;
					break;
				}
			}
		}
		// 根据题意：输出是 dp[N]
		return dp[N];
	}
}
